package cn.zhl.algorithm._1_排序;

/**
 * @program: demos
 * @description:
 * @author: 刘振华
 * @create: 2020-06-04 17:36
 **/
public class GuibingSort extends Sort{
	@Override
	protected void sort() {
		devide(0,array.length);
	}
	public void devide(int begin,int end){
		if(end - begin < 2){
			return;
		}
		int mid = (begin + end) >> 1;
		devide(begin,mid);
		devide(mid,end);
		merge(begin,mid,end);
	}
	public void merge(int begin,int mid,int end){
		int leftLen = mid-begin;
		int[] tmp = new int[leftLen];
		for(int i = 0;i<leftLen;i++){
			tmp[i] = array[begin+i];
		}
		int li = 0;
		int ri = mid;
		int ai = begin;
		while (li < leftLen && ri < end){
			if(array[ri] > tmp[li]){
				array[ai] = tmp[li];
				li++;
			}else{
				array[ai] = array[ri];
				ri++;
			}
			ai++;
		}
		if(ri >= end) {
			while (li<leftLen){
				array[ai++] = tmp[li++];
			}
		}
	}
}
